package com.sheepone.util.structure.tree.binary;

import com.sheepone.util.structure.tree.IndexedTree;

import java.util.*;

/**
 * @author Miss.杨
 * @description
 * @since 2024/5/8 - 11:00
 */
public class IndexedBinaryTree<E> extends IndexedTree<E> implements BinaryTree<E> {
    public IndexedBinaryTree(int capacity) {
        super(capacity);
    }

    protected int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    protected int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    protected int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    @SuppressWarnings("all")
    @Override
    public List<List<E>> layerTransfer() {
        ArrayList<List<E>> transfer = new ArrayList<>();
        if (isEmpty()) {
            return transfer;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int index, level, child, s;
        ArrayList<E> list = null;
        while (!queue.isEmpty()) {
            list = new ArrayList<>();
            transfer.add(list);
            // 当前层的节点数
            s = queue.size();
            for (int i = 0; i < s; i++) {
                index = queue.poll();
                list.add(elements[index]);
                child = getLeftChildIndex(index);
                if (isEffectiveIndex(child)) {
                    queue.offer(child);
                }
                child = getRightChildIndex(index);
                if (isEffectiveIndex(child)) {
                    queue.offer(child);
                }
            }
        }
        return transfer;
    }

    @Override
    public List<E> preOrderTransfer() {
        if (isEmpty()) {
            return null;
        }
        ArrayList<E> transfer = new ArrayList<>();
        Stack<Integer> istack = new Stack<>();
        int index = 0;
        while (isEffectiveIndex(index) || !istack.isEmpty()) {
            while (isEffectiveIndex(index)) {
                istack.add(index);
                // 遍历时直接存储值
                transfer.add(elements[index]);
                index = getLeftChildIndex(index);
            }
            // 当前索引节点没有左子节点
            if (!istack.isEmpty()) {
                index = getRightChildIndex(istack.pop());
            }
        }
        return transfer;
    }

    @Override
    public List<E> inOrderTransfer() {
        if (isEmpty()) {
            return null;
        }
        ArrayList<E> transfer = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        while (isEffectiveIndex(index) || !stack.isEmpty()) {
            // 一直遍历所有的左子节点，直到无左叶子节点
            while (isEffectiveIndex(index)) {
                stack.add(index);
                index = getLeftChildIndex(index);
            }
            if (!stack.isEmpty()) {
                index = stack.pop();
                transfer.add(elements[index]);
                // 指针指向右叶子节点
                index = getRightChildIndex(index);
            }
        }
        return transfer;
    }

    @Override
    public List<E> postOrderTransfer() {
        if (isEmpty()) {
            return null;
        }
        ArrayList<E> transfer = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int index, child;
        // 入栈顺序：根节点、左子节点、右子节点
        stack.push(0);
        while (!stack.isEmpty()) {
            // 出栈顺序：1.根节点
            index = stack.pop();
            transfer.add(elements[index]);
            // 出栈顺序：3.左子节点
            child = getLeftChildIndex(index);
            if (isEffectiveIndex(child)) {
                stack.push(child);
            }
            // 出栈顺序：2.右子节点
            child = getRightChildIndex(index);
            if (isEffectiveIndex(child)) {
                stack.push(child);
            }
        }
        // 反序出栈顺序：左子节点、右子节点、根节点
        Collections.reverse(transfer);
        return transfer;
    }

    /**
     * 是否对称
     *
     * @return
     */
    @Override
    public boolean isSymmetrical() {
        if (isEmpty()) {
            return true;
        }
        return isSymmetrical(getLeftChildIndex(0), getRightChildIndex(0));
    }

    private boolean isSymmetrical(int leftIndex, int rightIndex) {
        if (!isEffectiveIndex(leftIndex) && !isEffectiveIndex(rightIndex)) {
            return true;
        }
        if (!isEffectiveIndex(leftIndex) || !isEffectiveIndex(rightIndex)) {
            return false;
        }
        if (!elements[leftIndex].equals(elements[rightIndex])) {
            return false;
        }
        return isSymmetrical(getLeftChildIndex(leftIndex), getRightChildIndex(rightIndex))
                && isSymmetrical(getLeftChildIndex(rightIndex), getRightChildIndex(leftIndex));
    }

    /**
     * 默认采用层序遍历获取二叉树层数
     *
     * @return
     */
    @Override
    public int layers() {
        return maxDepth();
    }

    /**
     * 层序遍历求最大深度
     *
     * @return 最大深度
     */
    @Override
    @SuppressWarnings("all")
    public int maxDepth() {
        if (isEmpty()) {
            return 0;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int depth = 0, index, left, right;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                index = queue.poll();
                left = getLeftChildIndex(index);
                right = getRightChildIndex(index);
                if (isEffectiveIndex(left)) {
                    queue.offer(left);
                }
                if (isEffectiveIndex(right)) {
                    queue.offer(right);
                }
            }
            depth++;
        }
        return depth;
    }


    /**
     * 层序遍历求最小深度
     *
     * @return 最小深度
     */
    @Override
    public int minDepth() {
        if (isEmpty()) {
            return 0;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int depth = 1, index, left, right;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                index = queue.poll();
                left = getLeftChildIndex(index);
                right = getRightChildIndex(index);
                if (!isEffectiveIndex(left) && !isEffectiveIndex(right)) {
                    return depth;
                }
                if (isEffectiveIndex(left)) {
                    queue.offer(left);
                }
                if (isEffectiveIndex(right)) {
                    queue.offer(right);
                }
            }
            depth++;
        }
        return depth;
    }
}
